#include <stdio.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
typedef char datatype;

typedef struct stack
{
    datatype* a;
    int top;
    int capcity;
}stack;
void StackInit(stack* st)
{
    st->a = NULL;
    st->top = 0;
    st->capcity = 0;
}

void StackPush(stack* st, datatype x)
{
    assert(st);
    if (st->top == st->capcity)
    {
        int newcapcity = st->capcity == 0 ? 4 : 2 * st->capcity;
        datatype* tem = (datatype*)realloc(st->a, newcapcity * sizeof(datatype));
        if (tem == NULL)
        {
            perror("realloc  fail");
            return;
        }
        st->a = tem;
        st->capcity = newcapcity;
    }
    st->a[st->top] = x;
    st->top++;
}
bool StackEmpty(stack* st)
{
    assert(st);
    return st->top == 0;
}
void StackPop(stack* st)
{
    assert(st);
    assert(!StackEmpty(st));
    st->top--;
}
datatype StackTop(stack* st)
{
    assert(st);
    assert(!StackEmpty(st));
    return st->a[st->top - 1];
}

void StackDestroy(stack* st)
{
    free(st->a);
    st->a = NULL;
    st->top = 0;
    st->capcity = 0;
}


bool isValid(char* s) {

    int size = strlen(s);
    stack ps;
    StackInit(&ps);
    bool ismatch = true;
    for (int i = 0; i < size; i++)
    {
        if ('(' == s[i] || '[' == s[i] || '{' == s[i])
        {
            StackPush(&ps, s[i]);
        }
        else
        {
            if (StackEmpty(&ps))
            {
                //StackDestroy(&st);
                //return false;
                ismatch = false;
                break;
            }
            char top = StackTop(&ps);
            if ((top == '(' && s[i] == ')') ||
                (top == '[' && s[i] == ']') ||
                (top == '{' && s[i] == '}'))
            {
                StackPop(&ps);
            }
            else {
                ismatch = false;
                break;
            }
        }
        if (!StackEmpty(&ps))
        {
            ismatch = false;
        }
        StackDestroy(&ps);
        return ismatch;

    }
}